package Hot100.leetcode.editor.cn.code.二分;

import java.util.LinkedHashMap;
import java.util.Map;

//Java：LRU 缓存
public class LruCache{
    public static void main(String[] args) {
        LRUCache solution = new LruCache().new LRUCache(2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class LRUCache {
        //访问顺序模式
        //需要通过特殊构造函数创建：
        //private final Map<Integer, Integer> cache = new LinkedHashMap<>(16, 0.75f, true);
        //在这种模式下：
        //元素按照访问顺序排列
        //每次访问元素（get、put等操作）都会将该元素移到链表末尾
        //链表头部始终是最近最少使用的元素
    private final int capacity;
    private final Map<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        //删除key并利用返回值判断key是否在cache中
        Integer value = cache.remove(key);
        if(value != null){//说明key是存在的
            cache.put(key, value);//我们把这个节点提到最前来
            return value;
        }
        return -1;//key不在
    }
    
    public void put(int key, int value) {
        //同理利用返回值判断是否存在注意一定是要删除的不然无法提前
        //1.已经存在我们更新值并提前
        if(cache.remove(key) != null){
            cache.put(key, value);
            return;
        }
        //2.如果不存在就需要插入并需要判断容量
        if(cache.size() == capacity){
            //当容量满时，需要移除最久未使用的元素，也就是链表头部的元素。
            Integer eldestkey = cache.keySet().iterator().next();//获取迭代器的第一个元素
            cache.remove(eldestkey);
        }
        cache.put(key, value);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}